package cn.hughie.uf;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * 加权+路径压缩 并查集
 *
 * @author yuh
 * @date 2018/5/14 14:24
 */
public class QuickUnionFind {

    /**
     * 节点的root
     */
    private int[] id;
    /**
     * root对应的分量的大小
     */
    private int[] sz;
    /**
     * 分量的个数
     */
    private int count;

    /**
     * 节点数
     *
     * @param n 节点的个数
     */
    public QuickUnionFind(int n) {
        id = new int[n];
        sz = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        count = n;
    }

    /**
     * 返回p对应的根节点
     *
     * @param p 指点节点
     * @return
     */
    public int find(int p) {

        while (id[p] != p) {
            //路径压缩 非递归压缩
            p = id[p] = id[id[p]];
        }

       /* if (id[p] != p) {
            id[p] = find(p);
        }*/
        return p;
    }

    /**
     * 是否相连接
     *
     * @param p 节点p
     * @param q 节点q
     * @return
     */
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 结合两个节点
     *
     * @param p 节点p
     * @param q 节点q
     */
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (sz[pRoot] > sz[qRoot]) {
            id[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        } else {
            id[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        count--;
    }

    public static void main(String[] args) {
        int n = 100000;
        QuickUnionFind quickUnionFind = new QuickUnionFind(n);
        Random random = new Random(100000L);
        quickUnionFind.union(1, 2);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 10000; i++) {
            int r1 = random.nextInt(100000);
            int r2 = random.nextInt(100000);
            quickUnionFind.union(r1, r2);
            map.put(r1, r2);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            boolean connected = quickUnionFind.isConnected(entry.getKey(), entry.getValue());
            if (!connected) {
                throw new RuntimeException("Error!!!");
            }
        }
    }
}
